Vanessa and the O's formed in 2003/2004 when Vanessa Contenay-Quinones got together with Swedes Andreas Mattson (Popsicle) and Niclas Frisk (Atomic Swing) later joining up with James Iha (former guitarist and co-founding member of The Smashing Pumpkins) in New York.
They recorded the album La Ballade d'O over the next 18 months. Quinones also went into the studio with Lou Reed around this time and cut an Anglo/French version of "Sunday Morning" under the name 'Vanessa St James ft Lou Reed'. The album was finally finished in 2005 when Pelle Gunnerfeldt (producer of The Hives) was brought in for additional production and mixes, bringing in Per Nordmark on drums and Bjorn Ytlling (of Peter Bjorn & John) for additional keyboards. The self-financed album was licensed initially to Virgin/EMI Sweden in May 2005.
In September 2005, the imported the debut was 'Album of the Week' in influential London record store Rough Trade who described it as "...a fantastic album of ‘European cool’ with breathy vocals over music which sounds like The Concretes, Stereolab or a modern take on the Velvet Underground…" In 2006 the band decided to release the album on their own label Rushmore Recordings headed up by ex Warner Bros A&R executive and Deaf School founder member Steve Allen. By summer 2007 the album was available in France, Japan, Thailand, Portugal, Finland, Norway, Denmark and Sweden and digitally worldwide earning great critical acclaim with a 'Disque Du Mois' from influential French rock mag 'Rock & Folk' saying "Incontournable!...un album estival, lumineux, en teintes blanches, jaunes et pourpres...c'est un miracle..Vanessa a la classe total!" (Nicolas Ungermuth)and rave reviews from the other leading french music writers on Les Inrockuptibles, Magic, Rolling Stone and Figaro. The O's played live shows in Sweden, France, Japan, Holland and the UK through 2006/2007/08.
In 2006, Vanessa was the guest vocalist on Scott Walkers album The Drift.
2007 saw The O's invited to participate in the all-star musical tribute to legendary composer Ennio Morricone alongside Bruce Springsteen, Metallica, Yo Yo Ma, Quincy Jones, Herbie Hancock and Ennio Morricone. "We All Love Ennio Morricone" features Vanessa & The O's rendition of the Morricone/Françoise Hardy classic "Je Changerais d'Avis".
In 2008, the second in the all female French pop series, Filles Fragiles, included the new Vanessa Contenay-Quinones song, "Pres de Toi", taken from her solo side project Allez Pop!. In 2009, the Italian compilation release, Paris Fashion District Vol 2 featured new Vanessa Contenay-Quinones/Allez Pop! track "Magnifique". In 2010, Paris Fashion District Vol 3 featured "Pres de Toi" and the Supperclub series featured "Oddysee" taken from Vanessa's Allez Pop! project which also provided the track "Quand Tu Me Dis (Doop Doop)" for the French pop compilation Musique Fantastique from the Netherlands.
In 2009/2010, Vanessa and Andreas Mattsson hooked up with Robyn keyboardist Markus Jagerstedt to work on the second Vanessa & The O's album, writing and recording new songs in London and Stockholm with final mixes undertaken by Pelle Gunnerfeldt in March 2010.